#include"BinaryTree.h"

template<typename T>
class RedBlackTree;

template<typename T>
class RedBlackTree : public BinaryTree<T>
{
public:
    typedef typename BinaryTree<T>::Node Node;

    RedBlackTree(T _data) : BinaryTree<T>(_data)
    {
        this->root->color = BLACK;
    };

    RedBlackTree(){};

    int insert(Node* _new);
    int insert(T _data);
    int del(Node* _x);
};

template<typename T>
int RedBlackTree<T>::insert(Node* _new)
{
    Node* x = _new;
    if(this->root == this->nil)
    {
        this->root = x;
        this->root->color = BLACK;
        return 0;
    }
    BinaryTree<T>::insert(x);
    if(x->parent->color == BLACK)
    {
        this->root->color = BLACK;
        return 0;
    }
    while(x->parent != this->nil && x->parent->color == RED)
    {
        if(x->parent == x->parent->parent->lc)
        {
            Node* y = x->parent->parent->rc;
            if(y != this->nil && y->color == RED)
            {
                x->color = RED;
                x->parent->color = y->color = BLACK;
                y->parent->color = RED;
                x = y->parent;
            }
            else
            {
                if(x == x->parent->rc)
                {
                    this->LeftRotate(x->parent);
                    x = x->lc;
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                this->RightRotate(x->parent->parent);
            }
        }
        else if(x->parent == x->parent->parent->rc)
        {
            Node* y = x->parent->parent->lc;
            if(y != this->nil && y->color == RED)
            {
                x->color = RED;
                x->parent->color = y->color = BLACK;
                y->parent->color = RED;
                x = y->parent;
            }
            else
            {
                if(x == x->parent->lc)
                {
                    this->RightRotate(x->parent);
                    x = x->rc;
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                this->LeftRotate(x->parent->parent);
            }
        }
    }
    return 0;
};

template<typename T>
int RedBlackTree<T>::insert(T _data)
{
    Node *t = new Node(_data);
    insert(t);
    return 0;
};

template<typename T>
int RedBlackTree<T>::del(Node* _x)
{
    Node* y = _x;
    bool original_color_y = y->color;
    Node* x;
    if(x->lc == this->nil)
    {
        x = _x->rc;
        this->transplant(_x, _x->rc);
    }
    else if(_x->right == this->nil)
    {
        x = _x->lc;
        this->transplant(_x, _x->lc);
    }
    else
    {
        y = this->min(_x->rc);
        original_color_y = y->color;
        x = y->rc;
        if(y->parent != _x)
        {
            this->transplant(_x, y);
            y->rc = _x->rc;
            y->rc->parent = y;
        }
        this->transplant(_x, y);
        y->lc = _x->lc;
        y->lc->parent = y;
        y->color = _x->color;
    }
    if(original_color_y == BLACK)
    {
        while (x != this->root && x->color == BLACK)
        {
            if(x == x->parent->lc)
            {
                Node* w = x->parent->rc;
                if(w->color == RED)
                {
                    w->color = BLACK;
                    x->parent->color = RED;
                    this->LeftRotate(x->parent);
                    w = x->parent->rc;
                }
                if(w->lc->color == BLACK && w->rc->color == BLACK)
                {
                    w->color = RED;
                    x = x->parent;
                }
                else
                {
                    if(w->rc->color == BLACK)
                    {
                        w->lc->color = BLACK;
                        w->color = RED;
                        this->RightRotate(w);
                        w = x->parent->rc;
                    }
                    w->color = x->parent->color;
                    x->parent->color = BLACK;
                    w->rc->color = BLACK;
                    this->LeftRotate(x->parent);
                    x = this->root;
                }
            }
            else
            {
                Node* w = x->parent->lc;
                if(w->color == RED)
                {
                    w->color = BLACK;
                    x->parent->color = RED;
                    this->RightRotate(x->parent);
                    w = x->parent->lc;
                }
                if(w->rc->color == BLACK && w->lc->color == BLACK)
                {
                    w->color = RED;
                    x = x->parent;
                }
                else
                {
                    if(w->lc->color == BLACK)
                    {
                        w->rc->color = BLACK;
                        w->color = RED;
                        this->RightRotate(w);
                        w = x->parent->lc;
                    }
                    w->color = x->parent->color;
                    x->parent->color = BLACK;
                    w->lc->color = BLACK;
                    this->RightRotate(x->parent);
                    x = this->root;
                }
            }
        }
        x->color = BLACK;
    }
}